
"""扩展欧几里得"""
def exgcd(a, b):
    if 0 == b:
        return 1, 0, a
    x, y, q = exgcd(b, a % b)
    x, y = y, (x - a // b * y)
    return x, y, q
"""扩展中国剩余定理"""
def crt(n,a,m):
    if n == 1:
        if m[0] > a[0]:
            return a[0];
        else:
            return -1;

    for i in range(n):
        if m[i] <= a[i]:
            return -1;
        x, y, d = exgcd(m[0], m[i])
        if (a[i] - a[0]) % d != 0:
            return -1;

        t = m[i] // d;
        x = (a[i] - a[0]) // d * x % t
        a[0] = x * m[0] + a[0];
        m[0] = m[0] * m[i] // d;
        a[0] = (a[0] % m[0] + m[0]) % m[0]
        # print(a[0])
    return a[0];

n1= 1904313132335553332563685640224501316195060387039291454258452657299821538626735989493633983166720104217906850724297422905386250118815390783778373130982501216186565806218413706810373737826812052732515316227
n2= 2081212402787314500762252532904754336373063108132323763913408124916283326311311086247668153397845776240607423386320395552712872826748488036200057702186911826955275205171379436467643966507303879412715388417
c1= 146822144924317933479803034634922706093216428349697245803232931101484754036831548165333255387044190888525919724536111520190503320074503845896398342343466020973345780819882902367082602135401975062012075491
c2= 1567206971447556732505405347544299472008268564665307946088792360700095261216102457334780804905677091772881892154862377425268658425350748418690599174682298546862528649420909809375619107070854365785712028666

a=3767
b=3691
e = 65535
import libnum
q=libnum.gcd(n1,n2)
p=n1//q
r=n2//q
phi=(p-1)*(q-1)*(r-1)
d,s,s1=libnum.xgcd(e,phi)
c=crt(2,[c1,c2],[n1,n2])
m=pow(c,d,p*q*r)
print(m)
m=libnum.nroot(m,s1)
print(m)
for i in range(q-b+1,q-1):
    m=(m*i)%q
for i in range(p-a+1,p-1):
    m=(m*i)%p
print(m)
print(libnum.n2s(int(m)))